home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 101-125 / disk_105 / bison / closure.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  8KB  |  384 lines
  1. /* Subroutines for bison, copyright (C) 1984 Bob Corbett and Richard Stallman
  2.  
  3.    Permission is granted to anyone to make or distribute verbatim copies of this program
  4.    provided that the copyright notice and this permission notice are preserved;
  5.    and provided that the recipient is not asked to waive or limit his right to
  6.    redistribute copies as permitted by this permission notice;
  7.    and provided that anyone possessing an executable copy
  8.    is granted access to copy the source code, in machine-readable form,
  9.    in some reasonable manner.
  10.  
  11.    Permission is granted to distribute derived works or enhanced versions of
  12.    this program under the above conditions with the additional condition
  13.    that the entire derivative or enhanced work
  14.    must be covered by a permission notice identical to this one.
  15.  
  16.    Anything distributed as part of a package containing portions derived
  17.    from this program, which cannot in current practice perform its function usefully
  18.    in the absense of what was derived directly from this program,
  19.    is to be considered as forming, together with the latter,
  20.    a single work derived from this program,
  21.    which must be entirely covered by a permission notice identical to this one
  22.    in order for distribution of the package to be permitted.
  23.  
  24.  In other words, you are welcome to use, share and improve this program.
  25.  You are forbidden to forbid anyone else to use, share and improve
  26.  what you give them.   Help stamp out software-hoarding!  */
  27.  
  28. /* subroutines of file LR0.c.
  29.  
  30. Entry points:
  31.  
  32.   closure (items, n)
  33.  
  34. Given a vector of item numbers items, of length n,
  35. set up ruleset and itemset to indicate what rules could be run
  36. and which items could be accepted when those items are the active ones.
  37.  
  38. ruleset contains a bit for each rule.  closure sets the bits
  39. for all rules which could potentially describe the next input to be read.
  40.  
  41. itemset is a vector of item numbers; itemsetend points to just beyond the end
  42.  of the part of it that is significant.
  43. closure places there the indices of all items which represent units of
  44. input that could arrive next.
  45.  
  46.   initialize_closure (n)
  47.  
  48. Allocates the itemset and ruleset vectors,
  49. and precomputes useful data so that closure can be called.
  50. n is the number of elements to allocate for itemset.
  51.  
  52.   finalize_closure ()
  53.  
  54. Frees itemset, ruleset and internal data.
  55.  
  56. */
  57.  
  58. #include <stdio.h>
  59. #include "machine.h"
  60. #include "new.h"
  61. #include "gram.h"
  62.  
  63.  
  64. extern short **derives;
  65.  
  66.  
  67. short *itemset;
  68. short *itemsetend;
  69. static unsigned *ruleset;
  70.  
  71. /* internal data.  See comments before set_fderives and set_firsts.  */
  72. static unsigned *fderives;
  73. static unsigned *firsts;
  74.  
  75. /* number of words required to hold a bit for each rule */
  76. static int rulesetsize;
  77.  
  78. /* number of words required to hold a bit for each variable */
  79. static int varsetsize;
  80.  
  81.  
  82.  
  83. initialize_closure(n)
  84. int n;
  85. {
  86.   itemset = NEW2(n, short);
  87.  
  88.   rulesetsize = WORDSIZE(nrules + 1);
  89.   ruleset = NEW2(rulesetsize, unsigned);
  90.  
  91.   set_fderives();
  92. }
  93.  
  94.  
  95.  
  96. /* set fderives to an nvars by nrules matrix of bits
  97.    indicating which rules can help derive the beginning of the data
  98.    for each nonterminal.  For example, if symbol 5 can be derived as
  99.    the sequence of symbols 8 3 20, and one of the rules for deriving
  100.    symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */
  101.  
  102. set_fderives()
  103. {
  104.   register unsigned *rrow;
  105.   register unsigned *vrow;
  106.   register int j;
  107.   register unsigned mask;
  108.   register unsigned cword;
  109.   register short *rp;
  110.  
  111.   int ruleno;
  112.   int i;
  113.  
  114.   fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  115.  
  116.   set_firsts();
  117.  
  118.   rrow = fderives + ntokens * rulesetsize;
  119.  
  120.   for (i = ntokens; i < nsyms; i++)
  121.     {
  122.       vrow = firsts + ((i - ntokens) * varsetsize);
  123.       cword = *vrow++;
  124.       mask = 1;
  125.       for (j = ntokens; j < nsyms; j++)
  126.     {
  127.       if (cword & mask)
  128.         {
  129.           rp = derives[j];
  130.           while ((ruleno = *rp++) > 0)
  131.         {
  132.           SETBIT(rrow, ruleno);
  133.         }
  134.         }
  135.  
  136.       mask <<= 1;
  137.       if (mask == 0)
  138.         {
  139.           cword = *vrow++;
  140.           mask = 1;
  141.         }
  142.     }
  143.  
  144.       vrow += varsetsize;
  145.       rrow += rulesetsize;
  146.     }
  147.  
  148. #ifdef    DEBUG
  149.   print_fderives();
  150. #endif
  151.  
  152.   FREE(firsts);
  153. }
  154.  
  155.  
  156.  
  157. /* set firsts to be an nvars by nvars bit matrix indicating which items
  158.    can represent the beginning of the input corresponding to which other items.
  159.    For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
  160.    the symbol 8 can be the beginning of the data for symbol 5,
  161.    so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
  162.  
  163. set_firsts()
  164. {
  165.   register unsigned *row;
  166.   register int symbol;
  167.   register short *sp;
  168.   register int rowsize;
  169.  
  170.   int i;
  171.  
  172.   varsetsize = rowsize = WORDSIZE(nvars);
  173.  
  174.   firsts = NEW2(nvars * rowsize, unsigned);
  175.  
  176.   row = firsts;
  177.   for (i = ntokens; i < nsyms; i++)
  178.     {
  179.       sp = derives[i];
  180.       while (*sp >= 0)
  181.     {
  182.       symbol = ritem[rrhs[*sp++]];
  183.       if (ISVAR(symbol))
  184.         {
  185.           symbol -= ntokens;
  186.           SETBIT(row, symbol);
  187.         }
  188.     }
  189.  
  190.       row += rowsize;
  191.     }
  192.  
  193.   RTC(firsts, nvars);
  194.  
  195. #ifdef    DEBUG
  196.   print_firsts();
  197. #endif
  198. }
  199.  
  200.  
  201.  
  202. closure(core, n)
  203. short *core;
  204. int n;
  205. {
  206.   register int ruleno;
  207.   register unsigned word;
  208.   register unsigned mask;
  209.   register short *csp;
  210.   register unsigned *dsp;
  211.   register unsigned *rsp;
  212.  
  213.   short *csend;
  214.   unsigned *rsend;
  215.   int symbol;
  216.   int itemno;
  217.  
  218.   rsp = ruleset;
  219.   rsend = ruleset + rulesetsize;
  220.   csend = core + n;
  221.  
  222.   if (n == 0)
  223.     {
  224.       dsp = fderives + start_symbol * rulesetsize;
  225.       while (rsp < rsend)
  226.     *rsp++ = *dsp++;
  227.     }
  228.   else
  229.     {
  230.       while (rsp < rsend)
  231.     *rsp++ = 0;
  232.  
  233.       csp = core;
  234.       while (csp < csend)
  235.     {
  236.       symbol = ritem[*csp++];
  237.       if (ISVAR(symbol))
  238.         {
  239.           dsp = fderives + symbol * rulesetsize;
  240.           rsp = ruleset;
  241.           while (rsp < rsend)
  242.         *rsp++ |= *dsp++;
  243.         }
  244.     }
  245.     }
  246.  
  247.   ruleno = 0;
  248.   itemsetend = itemset;
  249.   csp = core;
  250.   rsp = ruleset;
  251.   while (rsp < rsend)
  252.     {
  253.       word = *rsp++;
  254.       if (word == 0)
  255.     {
  256.       ruleno += BITS_PER_WORD;
  257.     }
  258.       else
  259.     {
  260.       mask = 1;
  261.       while (mask)
  262.         {
  263.           if (word & mask)
  264.         {
  265.           itemno = rrhs[ruleno];
  266.           while (csp < csend && *csp < itemno)
  267.             *itemsetend++ = *csp++;
  268.           *itemsetend++ = itemno;
  269.         }
  270.  
  271.           mask <<= 1;
  272.           ruleno++;
  273.         }
  274.     }
  275.     }
  276.  
  277.   while (csp < csend)
  278.     *itemsetend++ = *csp++;
  279.  
  280. #ifdef    DEBUG
  281.   print_closure(n);
  282. #endif
  283. }
  284.  
  285.  
  286.  
  287. finalize_closure()
  288. {
  289.   FREE(itemset);
  290.   FREE(ruleset);
  291.   FREE(fderives + ntokens * rulesetsize);
  292. }
  293.  
  294.  
  295.  
  296. #ifdef    DEBUG
  297.  
  298. print_closure(n)
  299. int n;
  300. {
  301.   register short *isp;
  302.  
  303.   printf("\n\nn = %d\n\n", n);
  304.   for (isp = itemset; isp < itemsetend; isp++)
  305.     printf("   %d\n", *isp);
  306. }
  307.  
  308.  
  309.  
  310. print_firsts()
  311. {
  312.   register int i;
  313.   register int j;
  314.   register unsigned *rowp;
  315.   register unsigned cword;
  316.   register unsigned mask;
  317.  
  318.   extern char **tags;
  319.  
  320.   printf("\n\n\nFIRSTS\n\n");
  321.  
  322.   for (i = ntokens; i < nsyms; i++)
  323.     {
  324.       printf("\n\n%s firsts\n\n", tags[i]);
  325.  
  326.       rowp = firsts + ((i - ntokens) * vrowsize);
  327.  
  328.       cword = *rowp++;
  329.       mask = 1;
  330.       for (j = 0; j < nsyms; j++)
  331.     {
  332.       if (cword & mask)
  333.         printf("   %s\n", tags[j + ntokens]);
  334.  
  335.       mask <<= 1;
  336.  
  337.       if (mask == 0)
  338.         {
  339.           cword = *rowp++;
  340.           mask = 1;
  341.         }
  342.     }
  343.     }
  344. }
  345.  
  346.  
  347.  
  348. print_fderives()
  349. {
  350.   register int i;
  351.   register int j;
  352.   register unsigned *rp;
  353.   register unsigned cword;
  354.   register unsigned mask;
  355.  
  356.   extern char **tags;
  357.  
  358.   printf("\n\n\nFDERIVES\n");
  359.  
  360.   for (i = ntokens; i < nsyms; i++)
  361.     {
  362.       printf("\n\n%s derives\n\n", tags[i]);
  363.       rp = fderives + i * rrowsize;
  364.       cword = *rp++;
  365.       mask = 1;
  366.       for (j = 0; j <= nrules; j++)
  367.         {
  368.       if (cword & mask)
  369.         printf("   %d\n", j);
  370.  
  371.       mask <<= 1;
  372.       if (mask == 0)
  373.         {
  374.           cword = *rp++;
  375.           mask = 1;
  376.         }
  377.     }
  378.     }
  379.  
  380.   fflush(stdout);
  381. }
  382.  
  383. #endif
  384.